public class MyLinkedList implements LinkedList{

    static class ListNode {

        public int val;
        public ListNode prev;//前驱
        public ListNode next;//后继

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;//标记头

    public ListNode last;//标记尾巴

    MyLinkedList() {
        //last = head = new ListNode(-1);
    }

    @Override
    public void addFirst(int data) {
        ListNode node=new ListNode(data);
        if(head == null) {

            head = node;

            last = node;

        }else {

            node.next = head;

            head.prev = node;

            head = node;

        }

    }

    @Override
    public void addLast(int data) {
        ListNode node=new ListNode(data);
        if(head == null) {

            head = node;

            last = node;

        }else {

            last.next = node;

            node.prev = last;

            last = node;

        }
    }
    private ListNode searchIndex(int index) {

        ListNode cur = head;

        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;

    }
    @Override
    public boolean addIndex(int index, int data) {
        if(index < 0 || index > size()) {

            System.out.println("index不合法！");
            return false;

        }

        if(index == 0) {
            addFirst(data);

            return true;

        }

        if(index == size()) {

            addLast(data);

            return true;

        }
        ListNode cur=searchIndex(index);
        ListNode node=new ListNode(data);
        if(head!=null){
            node.next=cur;
            node.prev=cur.prev;
            cur.prev.next=node;
            cur.prev=node;
        }
        return true;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur=head;
        ListNode k=new ListNode(key);
        while (cur!=null){
            if(cur.val==k.val){
                return  true;
            }
            cur=cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        ListNode cur=head;
        while (cur != null) {

            if(cur.val == key) {
                //判断当前是不是头节点
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;//这里有问题！！！！ 一个节点！
                    }else {
                        last = null;
                    }
                }else {
                    //中间和尾巴的情况
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        last = last.prev;
                    }
                }
                return;//删完走人
            }else {
                cur = cur.next;
            }
        }
    }
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                //判断当前是不是头节点
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;//这里有问题！！！！ 一个节点！
                    }else {
                        last = null;
                    }
                }else {
                    //中间和尾巴的情况
                    cur.prev.next = cur.next;
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                    }else {
                        last = last.prev;
                    }
                }
                cur = cur.next;
            }else {
                cur = cur.next;
            }
        }
    }

    @Override
    public int size() {

        int count = 0;

        ListNode cur = head;

        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    @Override
    public void display() {
        ListNode cur = head;

        while (cur != null) {

            System.out.print(cur.val+" ");

            cur = cur.next;

        }

        System.out.println();
    }

    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null) {

            ListNode curNext = cur.next;

            ///cur.val = null;

            cur.prev = null;

            cur.next = null;

            cur = curNext;

        }

        head = null;

        last = null;

    }

    }

